In the field of data communication, data is typically compressed so that the amount of information being transmitted is reduced. Such data compression enables faster transmission due to the decreased data traffic. By decreasing data traffic, compression also reduces power consumption, which is especially important in communication to portable or mobile communication devices with limited battery capacity. In conventional communication between a server and a mobile communication device, requested data, such as message data, a website, or a digital file, is encoded, or compressed, by the server, and then transmitted. A decoder at the mobile communication device decodes the compressed data, and processes it appropriately, such as displaying it to the user.
In grammar-based compression technologies, such as Yang-Kieffer (YK) universal data compression, grammars are created on-the-fly. However, knowledge of previously communicated data, or knowledge of related grammars, can significantly improve compression performance. Such knowledge, falling within the definition of “side information”, which is any additional or related information that can be used to improve performance of coding or compression, can be used to augment encoders and decoders in the compression system. For example, in zlib, the sliding window can be primed with a predetermined dictionary of strings that are likely to occur in the data to be compressed (see e.g. J.- L. Gailly, “ZLIB compressed data format specification version 3.3,” RFC 1950, May 1996). The choice of the side information influences the compression ratio achieved by the compression system.
The compression ratio improves when the side information provided to the compression system is strongly correlated with the data to be compressed. However, practical constraints, such as the time, space and bandwidth needed to process, store and transmit the side information respectively, impose an upper limit on the amount of side information that can be handled or provided to the compression system. This limit will often be much less than the amount of data that is actually available. It is, therefore, desirable to provide a method that extracts a relatively small, but still strongly correlated, side information data sequence from a large candidate pool.